package leetcode_200;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;

/**
 *@author 周杨
 *BinaryTreeLevelOrderTraversalII_107 由低向高层次遍历二叉树
 *describe:用队列保存节点 数组保存每层的个数 反向输出即可  AC 96%
 *2018年5月20日 下午7:23:12
 */
public class BinaryTreeLevelOrderTraversalII_107 {
    List<List<Integer>> res;
	public static void main(String[] args) {
		BinaryTreeLevelOrderTraversalII_107 test=new BinaryTreeLevelOrderTraversalII_107();
		TreeNode root=new TreeNode(3);
		root.left=new TreeNode(9);
		root.right=new TreeNode(20);
		root.right.left=new TreeNode(15);
		root.right.right=new TreeNode(7);
		
		test.levelOrderBottom(root);

	}
	
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		this.res=new ArrayList<List<Integer>>();
		List<Integer> size=new ArrayList<Integer>();
		if(root==null) {
			return res;
		}
		int start=0;
		List<TreeNode> run=new ArrayList<TreeNode>();
		run.add(root);
		while(run.size()!=start) {
			int end=run.size();
			size.add(end-start);
			while(start!=end) {
				TreeNode now=run.get(start);
				if(now.left!=null)
					run.add(now.left);
				if(now.right!=null)
					run.add(now.right);
				++start;
			}
			start=end;
		}
		int index=run.size();
		int total=0;
		for(int i=size.size()-1;i>=0;--i) {
			int count=size.get(i);
            int temp=count;
			List<Integer> list=new ArrayList<Integer>();
			while(count>0) {
				list.add(run.get(index-count-total).val);
				--count;
			}
			this.res.add(list);
            total+=temp;
		}
		return res;
    }

}
